package com.kevinkk.dp;

import java.util.Scanner;

/**
 * 完全背包
 *
 * 0-1背包中 每个物品只能使用一次
 * 完全背包中 每个物品能够使用无限次
 *
 * 区别在于循环的遍历顺序
 * 0-1背包中
 *      采用二维 dp 数组时，遍历物品和背包的顺序可以相互交换
 *          dp 公式：dp[i][j] = max(dp[i-1][j], value[i]+dp[i-1][j-w[i]])
 *      采用一维 dp 数组时，只能先遍历物品、再遍历背包，【并且遍历背包时只能倒序遍历】‼️
 *          dp 公式：dp[j] = max(dp[j], value[i]+dp[j-w[i]])
 * 完全背包中
 *      采用二维 dp 数组时，遍历物品和背包的顺序可以相互交换
 *          dp 公式：dp[i][j] = max(dp[i-1][j], value[i]+dp[i][j-w[i]]) ‼️
 *      采用一维 dp 数组时，遍历物品和背包的顺序同样可以相互交换，【并且要顺序遍历背包】‼️
 *          dp 公式：dp[j] = max(dp[j], value[i]+dp[j-w[i]])
 */

public class UnboundedKnapsack{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), v = sc.nextInt();
        int[] weights = new int[n], value = new int[n];
        for(int i = 0; i < n; i++){
            weights[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int[] dp = new int[v+1];

        for(int i = 0; i < n; i++){
            for(int j = weights[i]; j <= v; j++){
                dp[j] = Math.max(dp[j], dp[j-weights[i]] + value[i]);
            }
        }

        System.out.println(dp[v]);
    }
}
